/*
 * Copyright 2008-2010 Digital Enterprise Research Institute (DERI)
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.sindice.rdfcommons.query;

import org.sindice.rdfcommons.storage.InMemoryResultSet;
import org.sindice.rdfcommons.storage.ResultSet;
import org.sindice.rdfcommons.model.Triple;
import org.sindice.rdfcommons.model.TripleBuffer;
import org.sindice.rdfcommons.model.TripleFilter;
import org.sindice.rdfcommons.model.TripleSet;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;


/**
 * Executes a {@link Query}.
 *
 * @author Michele Mostarda ( mostarda@fbk.eu )
 * @version $Id: TripleSetQueryExecutor.java 68 2011-01-09 15:44:31Z michele.mostarda $
 */
public class TripleSetQueryExecutor {

    /**
     * Creates a match between a triple, the previous match and the current one.
     * 
     * @param t triple pattern.
     * @param previous previous match
     * @param current current match.
     * @return new {@link org.sindice.rdfcommons.query.Match} instance.
     */
    protected static Match createMatch(Triple t, Match previous, Match current) {
        if(previous == null) {
            return current;
        }
        String[] currVars = current.getVars();
        String value  = null;
        String sub = null;
        String pred = null;
        String obj = null;
        for(String currVar : currVars) {
            int prevVarIndex = previous.getVarIndex(currVar);
            int currVarIndex = current.getVarIndex(currVar);
            switch (prevVarIndex) {
                case -1:
                    value = currVar;
                    break;
                case 0:
                    value = t.getSubject();
                    break;
                case 1:
                    value = t.getPredicate();
                    break;
                case 2:
                    value = t.getObjectAsString();
                    break;
            }
            switch (currVarIndex) {
                case 0:
                    sub = value;
                    break;
                case 1:
                    pred = value;
                    break;
                case 2:
                    obj = value;
                    break;
            }
        }
        return new Match(current.getQueryContext(), sub, pred, obj);
    }

    /**
     * Progresses an index array starting from the <i>begin</i> pointer, returning <code>-1</code>
     * whether the progress sequence has been ended.
     *
     * @param begin pointer with the next index to be increased.
     * @param indexes list of indexes.
     * @param sets list of sets providing the upper bounds of every index.
     * @return the next index to be updated.
     */
    protected static int progressIndex(int begin, int[] indexes, TripleSet[] sets) {
        int i;
        for(i = begin; i < indexes.length; i++) {
            if(indexes[i] < sets[i].getSize() - 1) {
                indexes[i]++;
                return begin;
            } else {
                indexes[i] = 0;
            }
        }
        return i == indexes.length ? -1 : i;
    }


    /**
     * Multiplies a list of sets generated by a list of matches and return the result inside the given result set.
     *
     * @param matches
     * @param sets
     * @param rs
     */
    protected static void multiply(Match[] matches, TripleSet[] sets, InMemoryResultSet rs) {
        if(matches.length != sets.length) {
            throw new IllegalArgumentException();
        }

        int[] indexes = new int[sets.length];
        int cursor = 0;
        Match match;
        List<InMemoryResultSet.VarEntry> entries = new ArrayList<InMemoryResultSet.VarEntry>();
        while(cursor >= 0) {

            entries.clear();
            Set<String> processedVars = new HashSet<String>();
            for(int i = 0; i < matches.length; i++) {
                match = matches[i];
                List<Triple> triples = sets[i].getTriples();  // TODO: this MUST be optimized.
                Triple triple = triples.get(indexes[i]);

                if(match.isSubVar()) {
                    if( ! processedVars.contains(match.getSub()) ) {
                        entries.add( new InMemoryResultSet.VarEntry(triple.getSubject()) );
                        processedVars.add(match.getSub());
                    }
                }
                if(match.isPredVar()) {
                    if( ! processedVars.contains(match.getPred()) ) {
                        entries.add( new InMemoryResultSet.VarEntry(triple.getPredicate()));
                        processedVars.add(match.getPred());
                    }
                }
                if(match.isObjVar()) {
                    if( ! processedVars.contains(match.getObj()) ) {
                        if(triple.isObjectLiteral()) {
                            entries.add(
                                    new InMemoryResultSet.VarEntry(
                                        triple.getObject(),
                                        ResultSet.VariableType.LITERAL
                                    )
                            );
                        } else {
                            entries.add( new InMemoryResultSet.VarEntry(triple.getObjectAsString()) );
                        }
                        processedVars.add(match.getObj());
                    }
                }

            }

            rs.addResult( entries.toArray( new InMemoryResultSet.VarEntry[entries.size()] ) );

            cursor = progressIndex(cursor, indexes, sets);
        }
    }

    protected ResultSet filter(MatchChain qry, TripleSet in) {
        if(qry.isEmpty()) {
            throw new IllegalArgumentException("qry cannot be empty.");
        }

        InMemoryResultSet rs = new InMemoryResultSet( qry.getVars() );

        if(in.getSize() == 0) {
            return rs;
        }

        // Creating initial results.
        TripleSet matchSet = in.getTriples( new InternalFilter( qry.get(0) ) );
        Stack<TripleSet> partialResults = new Stack<TripleSet>();
        for(Triple triple : matchSet) {
            partialResults.push( new TripleBuffer(triple) );
        }

        Match previous = qry.get(0);
        Match currentMatch;
        TripleSet nextPartial;
        while( ! partialResults.isEmpty() ) {

            nextPartial = partialResults.peek();

            for(Triple triple : nextPartial) {

                boolean completed = true;
                for(int i = 1; i < qry.size(); i++) {

                    currentMatch = qry.get(i);

                    Match newMatch = createMatch(triple, previous, currentMatch);
                    matchSet = in.getTriples( new InternalFilter(newMatch) );

                    if(matchSet.getSize() == 0) {
                        completed = false;
                        // Removing incomplete results.
                        for(int j = 1; j < i; j++) {
                            partialResults.pop();
                        }
                        break;
                    }

                    partialResults.push(matchSet);

                }

                if(completed) {
                    TripleSet[] sets = new TripleSet[qry.size()];
                    for(int i = qry.size() - 1; i >= 0; i--) {
                        sets[i] = partialResults.pop();
                    }
                    multiply(qry.getMatches(), sets, rs);
                }

            }

        }

        return rs;
    }

    class InternalFilter implements TripleFilter {

        private Match match;

        InternalFilter(Match m) {
            match = m;
        }

        public boolean acceptTriple(Triple triple) {
            return
            ( match.isSubVar()  || triple.getSubject().equals( match.getSub())   )
                    &&
            ( match.isPredVar() || triple.getPredicate().equals(match.getPred()) )
                    &&
            ( match.isObjVar()  || triple.getObject().equals( match.getObj())    );

        }
    }


}
